1808C - Unlucky Numbers - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;

long long I[20], U[20];

long long cnt(long long x) {
	if(x == 0) return 0;
	long long maxx = 0, minx = 9;
	while(x) {
		maxx = max(maxx, x % 10ll);
		minx = min(minx, x % 10ll);
		x /= 10;
	}
	return maxx - minx;
}

int T, hst, a[20], b[20];
long long l, r, L[20], R[20];

int main() {
	I[0] = 1;
	for(int i = 1; i <= 18; i++)
		I[i] = I[i - 1] * 10 + 1;
	U[0] = 1;
	for(int i = 1; i <= 18; i++)
		U[i] = U[i - 1] * 10;
	scanf("%d", &T);
	while(T--) {
		scanf("%lld %lld", &l, &r);
		if(l == r) {
			printf("%lld\n", l);
			continue;
		}
		long long _l = l, _r = r;
		for(int i = 0; i <= 18; i++) {
			a[i] = _l % 10;
			b[i] = _r % 10;
			_l /= 10, _r /= 10;
		}
		L[0] = a[0], R[0] = b[0];
		for(int i = 1; i <= 18; i++)
			L[i] = L[i - 1] + U[i] * a[i], R[i] = R[i - 1] + U[i] * b[i]; 
		//for(int i = 0; i <= 18; i++)
		//	printf("%lld %lld\n", L[i], R[i]);
		hst = 18;
		while(a[hst] == 0 && b[hst] == 0)
			hst--;
		if(a[hst] == 0) {
			printf("%lld\n", 9 * I[hst - 1]);
			continue;
		}
		int nlcp = hst;
		while(a[nlcp] == b[nlcp]) nlcp--;
		long long ans = l;
		long long tmp;
		tmp = L[18] - L[nlcp] + I[nlcp] * a[nlcp];
		if(tmp >= l && cnt(tmp) < cnt(ans)) ans = tmp;
		if(nlcp > 0) {
			tmp = L[18] - L[nlcp - 1] + I[nlcp - 1] * a[nlcp - 1];
			if(tmp >= l && cnt(tmp) < cnt(ans)) ans = tmp;
			if(a[nlcp - 1] < 9) {
				tmp = L[18] - L[nlcp - 1] + I[nlcp - 1] * (a[nlcp - 1] + 1);
				if(cnt(tmp) < cnt(ans)) ans = tmp;
			}
		}
		tmp = R[18] - R[nlcp] + I[nlcp] * b[nlcp];
		if(tmp <= r && cnt(tmp) < cnt(ans)) ans = tmp;
		if(nlcp > 0) {
			tmp = R[18] - R[nlcp - 1] + I[nlcp - 1] * b[nlcp - 1];
			if(tmp <= r && cnt(tmp) < cnt(ans)) ans = tmp;
			if(b[nlcp - 1] > 0) {
				tmp = R[18] - R[nlcp - 1] + I[nlcp - 1] * (b[nlcp - 1] - 1);
				if(cnt(tmp) < cnt(ans)) ans = tmp;
			}
		}
		for(int i = a[nlcp] + 1; i < b[nlcp]; i++) {
			long long tmp = L[18] - L[nlcp] + I[nlcp] * i;
			if(cnt(tmp) < cnt(ans)) ans = tmp;
		}
		printf("%lld\n", ans);
	}
	
	return 0;
}